package danran.bfs;

import java.util.*;
import java.util.function.IntFunction;

/**
 * @Classname NumIslands
 * @Description TODO
 * @Date 2021/8/27 13:37
 * @Created by ASUS
 */
public class NumIslands {

    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
//                {'0','0','0','1','1'}
        };

        System.out.println(new NumIslands().numIslands(grid));
    }

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int numIslands(char[][] grid) {
        byte[][] isVisited = new byte[grid.length][grid[0].length];// default 0
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {// 当前为陆地
                    isVisited[i][j] = 1;
                    dfs(grid, i, j, isVisited);
                }
            }
        }
        int cnt = 0;
        for (char[] chars : grid) {
            for (char c : chars) {
                if (c == '1') cnt++;
            }
        }
        return cnt;
    }

    public void dfs(char[][] grid, int a, int b, byte[][] isVisited) {
        List<Integer> res = new ArrayList<>();
        Integer[] integers = res.toArray(new Integer[0]);
        for (int[] dir : dirs) {
            int x = a + dir[0];
            int y = b + dir[1];
            if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] == '0' || isVisited[x][y] == 1) {
                continue;// 越界跳过
            }
            grid[x][y] = 'X';
            isVisited[x][y] = 1;
            // dfs泛洪
            dfs(grid, x, y, isVisited);
        }
    }


}
